The graphics terminal of a Computer-Aided Engineering (CAE) workstation needs to produce accurate visual cues to the properties of an object if it is to adequately assist engineers in their designs. Typical properties include structure, shape, appearance, thermal gradients, and stress gradients. It is the function of the graphics subsystem of a CAE workstation to produce these images in a form that can be easily understood and manipulated.
With most methods of image synthesis, the image is generated by breaking the surfaces of the object into polygons, calculating the color and intensity values for each vertex, and drawing the results into a frame buffer while interpolating the color values across the polygon (Gouraud shading). The color information can be calculated from light source data or computed according to an analysis of a selected property.
The interpolation of coordinate and color (or intensity) values across each polygon must be performed quickly and accurately. This is accomplished by interpolating the coordinate value and color value of each quantized point (pixel) on the edges of the polygon and subsequently interpolating from edge to edge to generate the fill lines. If hidden surface removal with a Z buffer is required, then the depth (Z) value for each pixel must also be calculated. Furthermore, since color components can vary independently across a surfaces, values for red, green, and blue intensities must be interpolated independently. Thus, for a general purpose graphics system, a minimum of six different pixel values (X, Y, Z, Red, Green, and Blue) must be independently calculated when drawing polygons with Gouraud shading and interpolated Z values.
Generating the pixels and their values has traditionally been the bottleneck in image generation, because creating images at interactive speeds requires millions of pixels to be drawn per second. Alleviating the bottleneck requires an interpolation algorithm which can be implemented in hardware and extended to include six parameters. To maximize process overlap and minimize cost, it is desirable to have all components of the polygon rendering pipeline contained on a single chip.
The following disclosure describes a portion of a one-chip VLSI implementation of an interpolator (called the Polygon Rendering Chip, or PRC) capable of performing interpolated polygon fill with six parameters at rates up to twenty million pixels per second. Inputs for the PRC consist of polygon vertex data (X, Y, Z, R, G and B in form of 16-bit integers) and edge connectivity information fetched from an external dual-ported RAM. Its outputs are the X, Y, Z, R, G, and B data for each pixel. The PRC is capable of filling shaded polygons with over 2000 convex, concave, and/or crossing sides, and has an address space of 2.sup.15 by 2.sup.15 pixels.
The interpolation algorithm used in the PRC is related to the line-drawing algorithm described by Bresenham in the IBM Systems Journal, Vol. 4, No. 1, 1965. Unfortunately, Bresenham's algorithm imposes a restriction on the slope of the line to be interpolated. The lack of such a restriction, and the use of integer math for speed and ease of hardware implementation are among the distinguishing features of the new algorithm described herein, along with its VLSI implementation.
We shall briefly consider certain earlier line rendering interpolation algorithms. Each will be shown as a Pascal-like program. Unless otherwise noted, it will be assumed that X is the major axis and that its value increases. (It can be shown that by swapping X, Y and/or mirroring across the X and/or Y axis, any vector can be mapped into this assumption). Xs and Ys will be the starting values for X and Y. Xe and Ye will be the ending values for X and Y.
Digital Differential Analyzer
One prior art technique is the Digital Differential Analyzer (DDA). The DDA permits calculation of the Y value of a line without solving the equation Y=M*X+C (requiring a multiplication) for each value of X. This is accomplished by computing the line differential, or slope (M), as the constant (Ye-Ys)/(Xe-Xs). Once M has been computed, successive (X,Y) points can be generated by repeatedly incrementing X by one and adding M to Y. All Y values still need to be rounded to the nearest integer, but this is easily accomplished by adding 0.5 to the initial Y value and truncating each Y result. A down counter starting at Xe-Xs is also needed to detect the end of the line. Summarizing the above in program form we get:
______________________________________ PROCEDURE DDA1(Xs,Xe,Ys,Ye:INTEGER); VAR M,Y:REAL; N,X:INTEGER; BEGIN (* SETUP *) X := Xs; Y := Ys+.5; M := (Ye-Ys)/(Xe-Xs); N := (Xe-Xs); (* INTERPOLATION *) PLOT (X,INT(Y)); WHILE N&lt; &gt;0 DO BEGIN X := X+1; Y := Y+M; N := N-1; PLOT (X,INT(Y)); END; END; ______________________________________
The main difficulties in using the DDA are the initial divide to generate M, and the need to use real or fractional binary numbers for M and Y. Not only is the division generally slow, but it is prone to round-off errors. The fractional part of M and Y must have a precision at least equal to the screen precision to be guaranteed of hitting the correct end point, and some empirical data suggest that the precision must be at least twice that of the screen's precision to correctly draw all the points in between.
Bresenham's Algorithm
The DDA can be split into integer and fractional parts. The integer part includes the count value N, the X value, and the integer part of the Y value. The fractional part includes only the fractional part of the Y value and all of the slope M. Since we initially assumed X to be the major axis, the slope (Ye-Ys)/(Xe-Xs) will always be less than or equal to one.
The only connection between the fractional values and the integer values is the carry from the Y-fractional part to the Y-integer part. As long as any integer values generated by adding the slope M to the Y-fractional part are transferred to the Y-integer part, the integer and fractional parts can be treated independently. This can be done by subtracting one from the Y-fractional part and adding one to the Y-integer part whenever the Y-fractional part is greater than or equal to one. Since comparing for a condition of greater than or equal to zero (sign bit interrogation) is usually easier than comparing for the condition of greater than or equal to one, one can be subtracted from the initial Y-fractional part and the comparison to zero can be used. Letting Yf represent the Y-fractional part, and Yi represent the Y-integer part, our program becomes:
______________________________________ PROCEDURE DDA2(Xs,Xe,Ys,Ye:INTEGER); VAR M,Yf:REAL; N,X,Yi:INTEGER; BEGIN (* SETUP *) X := Xs; Yi := Ys; Yf := -.5; M := (Ye-Ys)/(Xe-Xs); N := (Xe-Xs); (* INTERPOLATION *) PLOT (X,Yi); WHILE N&lt;&gt;0 DO BEGIN X := X+1; Yf := Yf+M; IF Yf&gt;=0 THEN BEGIN Yf := Yf-1; Yi := Yi+1; END; N := N-1; Plot (X,Yi); END; END; ______________________________________
Since the values of the fractional parts are never used outside their own system of equations, they can all be scaled by the constant (2*(Xe-Xs). Only the boolean result of a compare for the condition of greater than or equal to zero is sent out. This has the result of eliminating the initial divide and converting all the fractional variables into integers. This is done without adding any multiplications other than by two, which can easily be accomplished with a left shift. Our program now becomes:
______________________________________ PROCEDURE BRESENHAM(Xs,Xe,Ys,Ye:INTEGER); VAR M,Yf, N,X,Yi:INTEGER; BEGIN (* SETUP *) X := Xs; Yi := Ys; Yf := -(Xe-Xs); M := 2*(Ye-Ys); N := (Xe-Xs); (* INTERPOLATION *) PLOT (X,Yi); WHILE N&lt; &gt;0 DO BEGIN X := X+1; Yf := Yf+M; IF Yf&gt;=0 THEN BEGIN Yf := Yf-2* (Xe-Xs); Yi := Yi+1; END; N := N-1; PLOT (X,Yi); END; END; ______________________________________
The above program is essentially the same as the rules Bresenham presented in his original article.
When using Bresenham's algorithm in X and Y only, the major axis should always be defined as the axis of greatest delta, thus ensuring that a point will be plotted for each pixel along the major axis. When interpolating along the Z, Red, Green, or Blue axes, the X (or Y) axis should remain the major axis, even though its delta may be smaller than delta Z, delta Red, delta Green, and/or delta Blue. This is because the line is projected onto the X-Y plane. For example, it would be absurd to take thousands of steps along the Z axis when only a few pixels are to be drawn! This implies that the slope of the line in the X-Z plane, for example, may be greater than one, a condition which would exclude using the Bresenham algorithm.
One approach many have used to implement Z, Red, Green, and Blue interpolation is to return to the DDA, which doesn't require the slope to be between zero and one. They claim that slight inaccuracies arising from the DDA in the Z, Red, Green, and Blue values are not as critical as those in X and Y.